#include<array>
#include<string>
using namespace std;
class Solution {
public:
    int minCut(string s) {
        int n=s.size();
        array<array<bool,2000>,2000>is_pal;
        for(int i=0;i<n;i++){
            for(int j=0;j<=i;j++){
                if(s[j]==s[i])
                    is_pal[j][i]=j>=i-1?true:is_pal[j+1][i-1];
                else 
                    is_pal[j][i]=false;
            }
        }
        array<int,2000>cut_dp;
        cut_dp.fill(INT_MAX);
        for(int i=0;i<n;i++){
            if(is_pal[0][i])cut_dp[i]=0;
            else{
                for(int j=i;j>=1;j--){
                    if(is_pal[j][i])
                        cut_dp[i]=min(cut_dp[i],cut_dp[j-1]+1);
                }
            }
        }
        return cut_dp[n-1];
    }
};